package com.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 39. 组合总和
 *
 * @author fy
 * @date 2022/4/28 20:39
 */
public class Solution39 {

    private List<List<Integer>> res;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        res = new ArrayList<>();
        combinationSum(candidates, target, 0, new ArrayList<>(), 0);
        return res;
    }

    private void combinationSum(int[] candidates, int target, int index, List<Integer> preList, int sum) {
        // 这里不需要传sum, 只需要每次减掉对应的值, 然后判断target是否为0
        if (sum > target) {
            return;
        }
        if (sum == target) {
            res.add(new ArrayList<>(preList));
        }
        for (int i = index; i < candidates.length; i++) {
            int candidate = candidates[i];

            sum += candidate;
            preList.add(candidate);
            combinationSum(candidates, target, i, preList, sum);
            preList.remove(preList.size() - 1);
            sum -= candidate;
        }
    }

}
